Seznami - osnove osnov

Seznami števil

1. podnaloga

Premisli, kaj počne spodaj navedena funkcija. Žal je rezultat domače naloge študenta 1. letnika, ki še ne ve, da funkcija brez komentarjev ni preveč ...

   def funk(seznam):
       j = 0            
       i = 0
       d = len(seznam)
       while i < d:    
           if seznam[i] == 1:      
               j += 1   
           i += 2
       return j

Predelaj jo (kar pomeni tudi, da jo opremiš s komentarji, ustrezno popraviš imena spremenljivk ...) v funkcijo prestej(n, seznam), ki v seznamu števil prešteje kolikokrat se v tem seznamu pojavi število n Na primer:

  >>> prestej(5,[2, 5, 12, 3, 5, 3, 12, 8, 12])
  2

Uradna rešitev

def prestej(n, seznam):
    '''kolikokrat v seznamu nastopa n'''
    vseh = 0            # na začetku je vseh 0
    i = 0
    dolSez = len(seznam)
    while i < dolSez:    # potujemo po vseh indeksih seznama
        if seznam[i] == n:      
            vseh += 1   # če je enak, povečamo št. vseh
        i += 1
    return vseh        # vrne koliko je bilo vseh parametrov n

2. podnaloga

Napiši funkcijo prestejSodeLihe(seznam), ki v seznamu števil prešteje kolikokrat se v tem seznamu pojavi sodo število. Rezultat naj vrne v obliki para (soda, liha) Na primer:

  >>> prestej([2, 5, 12, 3, 5, 3, 12, 8, 12])
  (5, 4)

Uradna rešitev

def prestejSodaLiha(n, seznam):
    '''koliko je v seznamu sodih in lihih'''
    sodih = 0            # na začetku je vseh sodih 0
    i = 0
    dolSez = len(seznam)
    while i < dolSez :    # potujemo po vseh indeksih seznama
        if seznam[i] % 2 == 0:      
            sodih += 1   # če je sodo
        i += 1
    return (sodih, dolSez - sodih)  # tako bo hitreje, kot če bi posebej šteli še lihe

3. podnaloga

Funkcija seznamMest(n,seznam)

   def seznamMest(n, seznam):
       '''indeksi, kje se v seznamu pojavi n '''
       i = 1
       while i <= len(seznam):    # potujemo po vseh indeksih seznama
           if seznam[i] == n:          # primerjamo ali je i-ti elt. enak n
               mesta.append([i])         # če pridemo do tega mesta, indeks dodamo k novemu seznamu
           i = i + 1
       return mesta                   # vrne nam seznam indeksov

vrnila seznam vseh mest, na katerih se v seznamu števil pojavi število n. Mesta štejemo od 0 dalje! Na primer:

  >>> seznamMest(12,[2, 5, 12, 3, 5, 3, 12, 8, 12])
  [2, 6, 8]

Žal ne dela prav. Ima sintaktične in semantične napake. Popravi jo!

Uradna rešitev

def seznamMest(n, seznam):
    '''indeksi, kje se v seznamu pojavi n '''
    mesta = []
    i = 0
    while i < len(seznam):    # potujemo po vseh indeksih seznama
        if seznam[i] == n:          # primerjamo ali je i-ti elt. enak n
            mesta.append(i)         # če pridemo do tega mesta, indeks dodamo k novemu seznamu
        i  += 1
    return mesta                   # vrne nam seznam indeksov

4. podnaloga

Funkcija kolikoEnic(seznamCelih) naj vrne seznam, kjer na mestu i povemo, koliko je v seznamu seznamCelih števil, ki imajo kot enice vrednost i. Na primer:

  >>> kolikoEnic([1432, 32155, 12, 351, 12353, 1255, 2313, 12, 8, 112])
  [0, 1, 4, 2, 0, 2, 0, 0, 1, 0]

saj v seznamu števil ni nobenega števila, ki bi imelo na mestu enic 0, je eno število (namreč 351), ki ima na mestu enic 1, 4 števila (1432, 12, 12 in 112), ki imajo na mestu enic 2 ....

Uradna rešitev

def kolikoEnic(seznamCelih):
    '''Preštejemo, koliko števil ima i enic'''
    števciEnic = [0] * 10 # vse možne enice
    i = 0
    while i < len(seznamCelih):    # potujemo po vseh indeksih seznama
        število = abs(seznamCelih[i])
        števciEnic[število % 10] += 1  # povećčamo ustrezni števec
        i += 1

    return števciEnic

Dolžina vektorja

Kot veste, je vektor v n razsežnem prostoru podan kot n-terka števil. Pojem dolžine lahko posplošimo in dobimo normo vektorja.

1. podnaloga

Najprej sestavimo funkcijo, ki izračuna "klasično" dolžino vektorja, torej njegovo Evklidsko normo.

 >>> dolzinaVektorja([1, 1])
 1.41421356237
 >>> dolzinaVektorja([1, 4, 2, -5])
 6.78232998313

Uradna rešitev

def dolzinaVektorja(vektor):
    ''' vrne dolžino vektorja v n-razsežnem prostoru '''
    vsotaKvadratov = 0
    i = 0
    while i < len(vektor):
        x = vektor[i]
        vsotaKvadratov += x**2
        i += 1
    return vsotaKvadratov**0.5

2. podnaloga

Sedaj pa sestavite funkcijo manhattanskaRazdalja(vektor), ki izračuna dolžino vektorja, podanega z geometrijo (ameriških) mestnih taksijev, oziroma njegovo prvo normo.

 >>> manhattanskaRazdalja([1, 1])
 2
 >>> manhattanskaRazdalja([1, 4, 2, -5])
 12

Uradna rešitev

def manhattanskaRazdalja(vektor):
    ''' vrne prvo normo vektorja v n-razsežnem prostoru '''
    vsota = 0
    i = 0
    while i < len(vektor):
        x = vektor[i]
        vsota += abs(x)
        i += 1
    return vsota

3. podnaloga

Zanimiva je tudi uniformna norma ali razdalja Čebiševa (tudi neskončna norma). Sestavi funkcijo neskoncnaNorma(vektor), ki izračuna to normo.

 >>> neskoncnaNorma([1, 1])
 1
 >>> neskoncnaNorma([1, 4, 2, -5])
 5

Uradna rešitev

def neskoncnaNorma(vektor):
    ''' vrne neskončno normo vektorja v n-razsežnem prostoru '''
    naj = abs(vektor[0]) # poiskati moramo navječjo abs. vrednost komponente
    i = 1
    while i < len(vektor):
        x = abs(vektor[i])
        if x > naj:  # našli smo boljšo
            naj = x
        i += 1
    return naj

Stopnice

1. podnaloga

V laboratoriju FMF-P1 jim je uspel tehnološki presežek. Sestavili so robota, ki zlahka hodi po stopnicah. Konkurenca na vsak način poskuša diskreditirati ta dosežek. Zato sestavljajo različne čudne kombinacije stopnic in čakajo, kdaj bo robot pri hoji padel, saj robot lahko prehodi le stopnico, ki je nižja od 20 cm. Ampak spretni študenti praktiki so robota opremili z merilnim sistemom, ki zmeri višino posamezne stopnice in napisali funkcijo (opaziš, da je lepo skrbno komentirana, kot vsa koda, ki jo pišejo v tem laboratoriju).

   def kolikoStopnic(stopnice):
       '''Koliko stopnic lahko prehodi robot'''
       katera = 0 # indeks stopnice
       while katera < len(stopnice):       
           v = stopnice[katera]            # za vsako stopnico vzamemo njeno visino 
           if v > 20:   # ce je visina stopnice na vrsti previsoka
               return katera # koliko stopnic lahko prehodim (ker začnemo z 0, bo OK!)
           katera += 1   # naslednja stopnica
       # prehodili smo vse !
       return len(stopnice)

Na osnovi te kode sestavi funkcijo kakoVisokoPridem(stopnice), ki kot argument prejme seznam višin stopnic stopnice rezultat, ki ga vrne, pa pove, na kakšni višini bo robot po koncu hoje.

Uradna rešitev

def kakoVisokoPridem(stopnice):
    '''kako visoko lahko lahko pride robot'''
    trenutnaVišina = 0             # zacnemo na visini 0
    katera = 0 # indeks stopnice
    while katera < len(stopnice):       
        v = stopnice[katera]            # za vsako stopnico vzamemo njeno visino 
        if v > 20:   # ce je visina stopnice na vrsti previsoka
            return trenutnaVišina # do sem sem prišel ...
        trenutnaVišina += v # stopimo višje!
        katera += 1   # naslednja stopnica
    # prehodili smo vse !
    return trenutnaVišina

2. podnaloga

Na FRI-P1 pa jim je uspelo izdelati napravo, ki zmoti merilni sistem robota tako, da meri višine stopnic, merjene od tal (ne od prejšnje stopnice). Ampak praktiki s FMF se ne dajo. Poleg tega, da robota izpopolnijo, da ima sedaj nastavljivo maksimalno višino koraka (a žal se ta med hojo ne da spreminjati), na osnovi prejšnje naloge napišejo funkcijo kakoVisoko(stopnice, korakRobota), ki kot argument prejme seznam višin stopnic stopnice, merjenih na "FRI način" in kako visoko se lahko robot premakne v enem koraku, rezultat, ki ga vrne, pa spet pove, kako visoko bo robot priplezal.

Primer:

 >>> kakoVisoko([5, 25, 45, 50, 76, 80, 81], 20)
 50

Uradna rešitev

def kakoVisoko(stopnice, korakRobota):
    '''Kako visoko bo pripezal robot'''
    trenutnaVišina = 0             # zacnemo na visini 0
    katera = 0
    while katera < len(stopnice):       # za vsako stopnico vzamemo njeno visino (od tal)
        v = stopnice[katera]            # kako visoko mora robot priti
        if v - trenutnaVišina <= korakRobota:   # ce je visina stopnice na vrsti manjša od korakRobota
            trenutnaVišina = v     # potem robot lahko stopi
        else:
            break                   # sicer ne preverjamo naprej in koncamo zanko
        katera += 1   # naslednja stopnica
 
    return trenutnaVišina